package KMP算法;

public class Solution {
    /*
    给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
     */
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty())
            return 0;
        // 求出模式串的next数组(前缀数组)
        int[] next = new int[needle.length()];
        getNext(next, needle);
        // 利用next数组进行KMP算法匹配
        int j = 0; // 指向模式串中的字符
        for (int i = 0; i < haystack.length(); i++) {
            // j需要回退到next数组中的位置,且需要满足当前回退的字符和haystack中的字符是相等的
            while (j > 0 && haystack.charAt(i) != needle.charAt(j))
                j = next[j - 1];
            if (haystack.charAt(i) == needle.charAt(j))
                j++;
            // 模式串已经完全匹配成功
            if (j == needle.length())
                return i - needle.length() + 1;
        }
        return -1;
    }


    public void getNext(int[] next, String s) {
        int j = 0; // i是后缀的末尾,j是前缀的末尾
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            // 当 s.charAt(i) != s.charAt(j) 时，需要回滚j(从next数组中向前寻找和next[i]相等的最长相等前后缀为多少)
            // next数组中数字的含义：以当前字符为前缀末尾的最长前后缀长度,包含当前字符
            while (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1]; // 不相等时回滚
            if (s.charAt(i) == s.charAt(j)) j++; // 相等时则最长前后缀长度加一
            next[i] = j; // j既表示前缀末尾,又表示当前字符的最长前后缀长度
        }
    }

    public void getNext2(int[] next, String s) {
        int j = -1; // i是后缀的末尾,j是前缀的末尾
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            // 不相等,回滚
            while (j > -1 && s.charAt(i) != s.charAt(j + 1)) j = next[j];
            // 相等时
            if (s.charAt(i) == s.charAt(j + 1)) j++;
            next[i] = j;
        }
    }
}
